Project Sekai - ✅-crypto-crack_the_safe

Project Sekai

🔒 UIUCTF 2023 / ✅-crypto-crack_the_safe

crack_the_safe - 500 points

Category: Crypto Description: I found this safe, but something about it seems a bit off - can you crack it? Files:

https://2023.uiuc.tf/files/26b28a6c5079a440230e3db0f2a1ecab/chal.py?token=eyJ1c2VyX2lkIjoxMTU5LCJ0ZWFtX2lkIjo2NTIsImZpbGVfaWQiOjQ5OH0.ZJ9wJw.IaO1K_dcJFqSdygo7CPgcAFM-QQ

Tags: crypto

Sutx pinned a message to this channel. 06/30/2023 5:15 PM

is dlog feasible?

17:26

seems running forever

@unpickled admin bot wants to collaborate

it is feasible

17:27

you need to cado it

sage doesnt produce result

17:28

oh

17:28

i dont have that tool

uh

17:29

theres a docker img

17:29

(doing a diff chal rn but i can run if you want)

17:29

(after i figure out args kek)

17:36

cado -dlp -ell=9213409941746658353293481 target=1798034623618994974454756356126246972179657041628028417881 4170887899225220949299992515778389605737976266979828742347 -t 6

running this in the background

k

uh

Image attachment

17:36

is cado supposed to

17:36

uh

hmm

(cado has to find log 2 then we have to do base conversion)

17:40

https://cothan.blog/post/discrete-log-with-cado-nfs/ ye i think im doing it right

Solving Elliptic Curve Discrete Log by CADO-NFS | Duc Tri Nguyen Blog

Learn how to use CADO-NFS to solve discrete log in weak elliptic curve crypto in CTF challenge

17:42

discrete_log(9213409941746658353293481,Mod(7,p)) sage cant even do this

yeah

17:42

i tried that

17:42

already

unpickled admin bot

discrete_log(9213409941746658353293481,Mod(7,p)) sage cant even do this

3615195244142833546243033

17:45

nvm

17:45

huh

wtf

17:45

why i didnt get it

17:45

peepoo

3615195244142833546243033

Image attachment

17:45

it is that

17:45

i didnt sage it

17:45

https://www.alpertron.com.ar/DILOG.HTM

Discrete logarithm calculator

Web application that finds discrete logarithms.

17:45

alpertron strong

seems not the answer

unpickled admin bot

3615195244142833546243033

.

17:47

its only for the 921

17:47

the large factor

17:47

we need to recover for rest and crt

what 921

9213409941746658353293481

17:48

largest factor of p-1

oh

then % 577 we have 209

17:50

sage: facs
{9213409941746658353293481: 3615195244142833546243033, 577: 209, 151: 38, 2: 0}
sage: factor(p-1)
2 * 19 * 151 * 577 * 67061 * 18279232319 * 111543376699 * 9213409941746658353293481
sage:

17:50

for the rest of them i got does not exist

17:52

crt is 595696634978874338665736257088 which is not key

yeah its not

17:52

doesn pass assert

ye

17:53

i assume its cuz the missing values

17:54

like 19, 67061, 18279232319, 111543376699, all dont have dlogs base 7 that are h (edited)

@Utaha wants to collaborate

ah how was the dlog

uh

unpickled admin bot

sage: facs
{9213409941746658353293481: 3615195244142833546243033, 577: 209, 151: 38, 2: 0}
sage: factor(p-1)
2 * 19 * 151 * 577 * 67061 * 18279232319 * 111543376699 * 9213409941746658353293481
sage:

i got these factors

18:06

but

18:06

:/

18:06

idk

didnt get dlog to work, idk

huh you factored the largest one, how can it not work lol

18:07

ok I'll do this

18:09

3615195244142833546243033 doesn't seem to be correct

unpickled admin bot

3615195244142833546243033

worked here?

uh

18:13

that's not how dlog works

18:15

like you are calculating g^x % q, where q is a prime factor of p-1

i found x for g^x % q?

but dlog is %p

owait

18:15

awkward

btw are you running cado

18:16

it took like an hour for me to build cado last time

18:16

forgot to build it in docker image :<

i do have a cado docker img set up

@kanon wants to collaborate

unpickled admin bot

cado -dlp -ell=9213409941746658353293481 target=1798034623618994974454756356126246972179657041628028417881 4170887899225220949299992515778389605737976266979828742347 -t 6

running this in the background

I'm running discrete log for 7

18:25

didn't find a way to specify the base

18:25

so probably need to do dlog for 7 as well

Utaha

I'm running discrete log for 7

ye

unpickled admin bot

https://cothan.blog/post/discrete-log-with-cado-nfs/ ye i think im doing it right

.

18:26

i tried doing the log2(h)/log2(7) as the article said but couldnt find log2(h)

idk how people solve it so quick lol

18:27

log(7) = 6424341129540508417798214 mod 941...

18:28

btw the key is at most 128 bits so we might be able to solve it partially

18:30

log base = 689700230313623370222183478814904246546188182712829892313 by cado's ouptut

18:30

didn't verify lol

Utaha

log base = 689700230313623370222183478814904246546188182712829892313 by cado's ouptut

wait what?

18:30

is this log2(7)

18:30

or log2(h)

log(7) and base is prob that huge number (edited)

oh im blind log base

log(h)/log(7) = 741784031885807265615861 mod 941 ... (edited)

18:33

nice

@Violin wants to collaborate

really close to solving

18:43

I feel like cado-nfs is slower for small prime factors lol

Utaha

used /ctf solve

✅ Challenge solved.

nice work

nice work @cado-nfs

gctf flashback

lmao true

Exported 105 message(s)